#
# @lc app=leetcode.cn id=921 lang=python3
#
# [921] 使括号有效的最少添加
#

# @lc code=start
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        left_cnt, insert_cnt, idx = 0, 0, 0
        while idx < len(s):
            match s[idx]:
                case '(':
                    left_cnt += 1
                    idx += 1
                case ')':
                    if left_cnt <= 0: # 需要插入左括号
                        insert_cnt += 1
                    else:
                        left_cnt -= 1
                    idx += 1
        insert_cnt += left_cnt

        return insert_cnt
    

# @lc code=end

